package P107_二叉树的层次遍历2;

import java.util.*;

/**
 * 107. 二叉树的层次遍历 II
 * 给定一个二叉树，返回其节点值自底向上的层次遍历。 （即按从叶子节点所在层到根节点所在的层，逐层从左向右遍历）
 * <p>
 * 例如：
 * 给定二叉树 [3,9,20,null,null,15,7],
 * <p>
 * 3
 * / \
 * 9  20
 * /  \
 * 15   7
 * 返回其自底向上的层次遍历为：
 * <p>
 * [
 * [15,7],
 * [9,20],
 * [3]
 * ]
 */
class TreeNode {
    int val;
    TreeNode left;
    TreeNode right;

    TreeNode(int x) {
        val = x;
    }
}

public class Solution {
    //     Queue<HashMap<Integer,TreeNode>> nodes= new LinkedList<>();
    public List<List<Integer>> levelOrderBottom(TreeNode root) {
        List<List<Integer>> ret = new ArrayList<>();
        if (root == null) {
            return ret;
        }
        LinkedList<TreeNode> curQueue = new LinkedList<>();
        curQueue.add(root);
        //广度优先遍历
        TreeNode cur;
        LinkedList<TreeNode> levelQueue = new LinkedList<>();
        while (!curQueue.isEmpty()) {
            List<Integer> level = new ArrayList<>();
            while ((cur = curQueue.pollFirst()) != null) {
                if (cur.left != null) levelQueue.add(cur.left);
                if (cur.right != null) levelQueue.add(cur.right);
                level.add(cur.val);
            }
            ret.add(0,level);
            curQueue.addAll(levelQueue);
            levelQueue.clear();
        }
        return ret;

    }

}
